/*
 * auction_matcher_impl.h
 *
 *  Created on: May 25, 2011
 *      Author: tqlong
 */

#ifndef AUCTION_MATCHER_IMPL_H_
#define AUCTION_MATCHER_IMPL_H_
#include "auction_matcher.h"
#include "../common/common.h"
#include <queue>

template<typename D1, typename D2>
AuctionMatcher<D1,D2>::AuctionMatcher(dataset1_type& data1, dataset2_type& data2, double r, double norm)
  : __Base(data1, data2), m_r(r), m_norm(norm)
{
  //m_X = new tree1_type(data1); m_X->buildTree();
  m_Y = new tree2_type(data2); m_Y->buildTree();
}

template<typename D1, typename D2>
void AuctionMatcher<D1,D2>::doMatch()
{
  int n1 = this->m_data1.n();
  int n2 = this->m_data2.n();
  int nn = n1+n2;
  m_price = vdouble_type(n2, 0);

  for (double epsilon = (double)nn/100; epsilon > 1.0/nn; epsilon /= 2)
    {
      Log::m_log << "epsilon=" << epsilon << endl;
      m_matchIdx  = vint_type(nn, -1);
      bool ok = true;
      m_count = 0;

      while (ok)
        {
          int yx = -1;
          double vx, wx;
          vdouble_type bid(n2, 0);
          vint_type winner(n2, -1);
          ok = false;

          // all free x bid
          for (int x = 0; x < this->m_data1.n(); x++)
            if (m_matchIdx[x] == -1)
              {
                findBest(x, yx, vx, wx);
                double a_bid = m_price[yx] + wx - vx + epsilon;
                if (bid[yx] < a_bid)
                  {
                    winner[yx] = x;
                    bid[yx] = a_bid;
                  }
                ok = true;
              }

          // all bidded y choose winner
          for (int y = 0; y < n2; y++)
            if (winner[y] != -1)
              {
                match(winner[y], y);
                m_price[y] = bid[y];
//                Log::m_log << "y=" << y << " win=" << winner[y] << endl;
              }
        } // while (ok)
      Log::m_log << endl;
    } // for epsilon
}

template<typename D1, typename D2>
void AuctionMatcher<D1,D2>::match(int x, int y)
{
  int n2 = this->m_data2.n();

  int x_old = m_matchIdx[y+n2];
  if (x_old != -1)
    m_matchIdx[x_old] = -1;
  else
    {
      m_count++;
      if (m_count % (n2 < 10 ? 1 : n2/10) == 0)
        {
          Log::m_log << m_count << " ";
          Log::m_log.flush();
        }
    }

  m_matchIdx[x] = y+n2;
  m_matchIdx[y+n2] = x;
}

template<typename D1, typename D2>
void AuctionMatcher<D1,D2>::findBest(int x, int &yx, double &vx, double &wx)
{
  int n2 = this->m_data2.n();
  yx = -1;
  vx = wx = POSITIVE_INFINITY;
//  Log::m_log << "x=" << x << " dxy: ";
  for (int y = 0; y < n2; y++)
    {
      double d = this->dist(x, y, m_norm);
      double dxy = d + m_price[y];
//      Log::m_log << dxy << " " << "(" << d << "," << m_price[y] << ") ";
      if (dxy < vx)
        {
          wx = vx;
          vx = dxy;
          yx = y;
        }
      else if (dxy < wx)
        {
          wx = dxy;
        }
    }
//  Log::m_log << endl << "yx=" << yx << " vx=" << vx << " wx=" << wx << endl;
}

#endif /* AUCTION_MATCHER_IMPL_H_ */
